This application claims the benefit of Korean Application No. 2001-54458 filed Sep. 5, 2001 in the Korean Industrial Property Office, the disclosure of which is incorporated herein by reference.
1. Field of the Invention
The present invention relates to a block-based moving picture coding method and system, and more particularly, to a method and system for estimating a motion vector at high speed for low bit-rate coding.
2. Description of the Related Art
In a typical block-based moving picture encoder, most bits to be transmitted are taken by frame residuals, in which motion is compensated for, and motion vector information. In particular, in low bit-rate encoding, the ratio of motion vector information to total data becomes greater because the motion vector information is not reduced while the frame residual components are reduced in order to achieve low bit-rate transmission . Therefore, it is disadvantageous that the relative ratio of the motion vector information to the total data is not reduced.
In the conventional Block Matching Algorithm (BMA), each Motion Vector (MV) {right arrow over (d)}=(dx, dy) is selected in a direction that minimizes encoding distortion, regardless of bit rates.
As shown in FIG. 1, which is a schematic diagram of a block matching algorithm, the motion vector MV of a predetermined block k is expressed by a coordinate difference between the block 102 of a current frame (t) and a matching block 104 of the previous frame (t-1). The matching block is found in a search region 106 centering around the current block. If a normal block size W is Nxc3x97N, the size xcexa9 of the search region 106 is (2W+1)xc3x97(2W+1).
The matching block in the search region 106 is a block in which the cost (not in the meaning of expense, but in the meaning of an error measure) is minimized, and is usually scanned in a raster scan method.
In general, the Sum of Absolute Differences (SAD) is frequently used as an error measure.
That is, among blocks in the search region 106, a block that satisfies the following formula 1 is determined as the matching block:                                                         min                                                                                            d                  →                                ∈                Ω                                                    ⁢                  SAD          ⁡                      (                          d              →                        )                                              (        1        )            
Where             SAD      ⁡              (                  d          →                )              =                  ∑                              r            →                    ∈          W                    ⁢              "LeftBracketingBar"                              I            ⁡                          (                                                r                  →                                ,                t                            )                                -                      I            ⁡                          (                                                                    r                    →                                    +                                      d                    →                                                  ,                                  t                  -                  1                                            )                                      "RightBracketingBar"              ,
and I({right arrow over (r)}, t) is a brightness value (illuminance) at position {right arrow over (r)} and frame t.
Recently, in order to improve the efficiency of low bit-rate moving picture encoding, instead of motion estimation methods of simply minimizing encoding distortion, motion estimation methods for minimizing encoding distortion under a limited bit-rate condition have been developed.
However, in these methods, a global search method should be used to estimate an accurate motion vector, and a great number of operations of the method are repeated until the motion vector is estimated. Therefore, it is impossible to encode moving pictures in real time.
To solve the above problems, it is an object of the present invention to provide an improved method and system for estimating a motion vector, in which the motion vector is estimated in a global search method at high speed.
Additional objects and advantageous of the invention will be set forth in part in the description which follows and, in part, will be obvious from the description, or may be learned by practice of the invention.
To accomplish the above and other objects of the present invention, there is provided a method of estimating a motion vector, the method including
(a) forming sum pyramids for a current block and search blocks of a search region;
(b) setting an initial Cmin to CL({right arrow over (d)}p;xcex) (where, Cl({right arrow over (d)}k;xcex) is an error measure at layer l which is determined by the following equation, and l and {right arrow over (d)} are 0 and (0,0), respectively:
Cl(dk;xcex)=SADl(dk)+xcexR(dk)
(c) if l is L, performing operation (d), if Cl({right arrow over (d)};xcex) greater than Cmin, performing operation (c) for a next candidate Motion Vector (MV) in the search region in a raster scanning method, after setting l to 0 (excluding (0,0) and {right arrow over (d)}p), and otherwise performing operation (c) after setting l to l+1;
(d) if CL({right arrow over (d)};xcex) less than Cmin, updating Cmin as CL({right arrow over (d)};xcex), if {right arrow over (d)} is the last candidate MV, performing operation (e), and otherwise performing operation (c) with the next candidate, after setting l to 0;
(e) estimating the MV by determining the MV having Cmin as an optimal matcher.